package twentytwentyone_3;

import java.awt.*;


/**
 * @Author: Zahi
 * @Description:
 * @Date Created in 2021-03-08 9:50
 * @Modified By:
 */
public class AAA {
    public static boolean pInQuadrangle(Point a, Point b, Point c, Point d, Point p) {
        double dTriangle = triangleArea(a, b, p) + triangleArea(b, c, p)
                + triangleArea(c, d, p) + triangleArea(d, a, p);
        double dQuadrangle = triangleArea(a, b, c) + triangleArea(c, d, a);
        return dTriangle == dQuadrangle;
    }

    // 如果在四边形内，则四边形的面积=面积(P,A,B)+面积(P,B,C)+面积(P,C,D)+面积(P,D,A);
    // 反之不在四边形内。
    public static boolean pInQuadrangle(float[] px, float[] py, float x, float y) {
        Point a = new Point((int) px[0], (int) py[0]);
        Point b = new Point((int) px[1], (int) py[1]);
        Point c = new Point((int) px[2], (int) py[2]);
        Point d = new Point((int) px[3], (int) py[3]);
        Point p = new Point((int) x, (int) y);
        double dTriangle = triangleArea(a, b, p) + triangleArea(b, c, p)
                + triangleArea(c, d, p) + triangleArea(d, a, p);
        double dQuadrangle = triangleArea(a, b, c) + triangleArea(c, d, a);
        return dTriangle == dQuadrangle;
    }

    // 返回三个点组成三角形的面积
    private static double triangleArea(Point a, Point b, Point c) {
        double result = Math.abs((a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y
                - c.x * b.y - a.x * c.y) / 2.0D);
        return result;
    }

    // 连锁挖矿  先做简单DFS模板
    void dfs(int[][] grid, int r, int c) {
        dfs(grid, r - 1, c); // 上边相邻
        dfs(grid, r + 1, c); // 下边相邻
        dfs(grid, r, c - 1); // 左边相邻
        dfs(grid, r, c + 1); // 右边相邻
    }
    // 加上递归和退出条件的判断，即遍历所有位置的情况
    void dfs1(int[][] grid, int r, int c) {
        // 若坐标不合法，直接返回
        if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) {
            return;
        }
        // 若该方格不是第一个挖矿挖到的值，直接返回
        if (grid[r][c] != 2) {
            return;
        }

        // 将已经遍历过的格子置为9
        grid[r][c] = 9;

        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
}
